from typing import List


class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        nums = []
        for pile in piles:
            while pile > 1:
                num = pile // 2
                pile -= num
                nums.append(num)

        nums.sort(reverse=True)

        return sum(nums[k:]) + len(piles)


if __name__ == "__main__":
    print(Solution().minStoneSum(piles=[5, 4, 9], k=2))  # 12
    print(Solution().minStoneSum(piles=[4, 3, 6, 7], k=3))  # 12
    print(Solution().minStoneSum(piles=[1], k=100000))  # 1
